package com.cong._474;

import javax.swing.plaf.IconUIResource;
import java.util.*;

public class Solution {
    public int findMaxForm(String[] strings, int zeros, int ones) {
        int len = strings.length;
        int[][] zeroOnes = new int[len][2];
        for(int i = 0;i < len; i++) {
            zeroOnes[i] = new int[2];
            for(char c: strings[i].toCharArray()) {
                zeroOnes[i][c - '0']++;
            }
        }
        Arrays.sort(zeroOnes, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int max = 0, remainZero = zeros, remainOnes = ones, curLen = 0;
        for(int index = 0;index < len; index++) {
            if (remainZero < 0 || remainOnes < 0) break;
            for(int i = index;i < len; i++) {
                int[] zeroOne = zeroOnes[i];
                if(i > index && zeroOne[0] == zeroOnes[i-1][0]) continue;
                if (zeroOne[0] <= remainZero && zeroOne[1] <= remainOnes) {
                    max = Math.max(max, curLen);
                    index = i;
                    remainZero -= zeroOne[0];
                    remainOnes -= zeroOne[1];
                    curLen++;
                    break;
                }
            }
        }
        return max;
    }
}

class Solution_2 {
    int max = 0;
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] counts = new int[len][2];
        for(int i = 0; i < len; i++) {
            counts[i] = count(strs[i]);
        }
        Arrays.sort(counts,(a,b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        backTrace(counts,0,m,n,0);
        return max;
    }

    private void backTrace(int[][] counts,int index,int m,int n,int currLength) {
        if(m < 0 || n < 0) return;
        for(int i = index; i < counts.length; i++) {
            int[] count = counts[i];
            if(i > index && count[0] == counts[i-1][0]) continue;
            if(count[0] <= m && count[1] <= n) {
                max = Math.max(max,currLength+1);
                backTrace(counts,i+1,m-count[0],n-count[1],currLength+1);
            }
        }
    }

    private int[] count(String s) {
        int oneCount = 0;
        int zeroCount = 0;
        int i = s.length() - 1;
        while(i >= 0) {
            char sc = s.charAt(i);
            if(sc == '1') {
                oneCount++;
            }
            else {
                zeroCount++;
            }
            i--;
        }
        return new int[]{zeroCount,oneCount};
    }
}

//public class Solution {
//    private static final Random r = new Random();
//    public int findMaxForm(String[] strings, int zeros, int ones) {
//        int maxLimit = zeros + ones;
//        Cell[][] map = new Cell[zeros + 2][ones + 2];
//        int[][] state = new int[zeros + 1][ones + 1];
//        // init map
//        for(String string: strings) {
//            int strLen = string.length();
//            if (strLen <= maxLimit) {
//                int strOnes = (int) string.chars().filter(it -> it == '1').count();
//                int strZeros = strLen - strOnes;
//                if (strOnes <= ones && strZeros <= zeros){
//                    state[strZeros][strOnes] += 1;
//                }
//            }
//        }
//
//        // init boundary of map
//        for(int i = 0; i < zeros + 2; i++) {
//            map[i][0] = new Cell(copyState(state),-1,0, 0);
//        }
//        for(int i = 0; i < ones + 2; i++) {
//            map[0][i] = new Cell(copyState(state), -1, 0, 0);
//        }
//        map[1][1] = new Cell(copyState(state), 0, 0, 0);
//
//        // fill the map
//        for (int z = 0; z <= zeros; z++) {
//            int zNumber = z + 1;
//            for(int o = 0; o <= ones; o++) {
//                int oNumber = o + 1;
//                if (z == 0 && o == 0) continue;
//                Cell left = map[zNumber][o];
//                Cell down = map[z][oNumber];
//                Cell chosen;
//                if (left.currentSize == down.currentSize) {
//                    chosen = randomChoice(left, down);
//                }else {
//                    chosen = left.currentSize > down.currentSize ? left : down;
//                }
//                Cell curCell = new Cell(chosen);
//                if (chosen == left) {
//                    curCell.remainOnes++;
//                }else {
//                    curCell.remainZeros++;
//                }
//                curCell.newStateIfMatch();
//                map[zNumber][oNumber] = curCell;
//            }
//        }
//        return map[zeros + 1][ones + 1].currentSize;
//    }
//
//    private static Cell randomChoice(Cell a, Cell b) {
////        int rand = r.nextInt(2);
////        return rand == 0 ? a : b;
//        return b;
//    }
//
//    private static int[][] copyState(int[][] originState) {
//        int rows = originState.length;
//        int[][] res = new int[rows][];
//        for(int i = 0; i < rows; i++) {
//            res[i] = Arrays.copyOf(originState[i], originState[i].length);
//        }
//        return res;
//    }
//
//    private static class Cell {
//        int[][] state;
//        int currentSize;
//        int remainZeros;
//        int remainOnes;
//
//        Cell (Cell c) {
//            state = c.state;
//            currentSize = c.currentSize;
//            remainZeros = c.remainZeros;
//            remainOnes = c.remainOnes;
//        }
//
//        Cell() {
//
//        }
//
//        Cell(int[][] state, int currentSize, int remainZeros, int remainOnes) {
//            this.state = state;
//            this.currentSize = currentSize;
//            this.remainZeros = remainZeros;
//            this.remainOnes = remainOnes;
//        }
//
//        void newStateIfMatch() {
//            if (state[remainZeros][remainOnes] > 0) {
//                int[][] newState = copyState(state);
//                newState[remainZeros][remainOnes]--;
//                this.state = newState;
//                this.currentSize++;
//                this.remainZeros = this.remainOnes = 0;
//            }
//        }
//    }
//
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        class Res {
//            final String[] inputStr;
//            final int inputZ;
//            final int inputO;
//            final int predict;
//            Res(String[] strings, int z, int o, int predict) {
//                inputStr = strings;
//                inputZ =z;
//                inputO = o;
//                this.predict = predict;
//            }
//        }
//        Res[] testCase = new Res[] {
//                new Res(new String[] {"10", "0001", "1", "0"}, 5, 3, 4),
//                new Res(new String[] {"001", "110","0000","0000"}, 9, 2, 3)
//        };
//        for (Res test: testCase) {
//            int maxForm = solution.findMaxForm(test.inputStr, test.inputZ, test.inputO);
//            System.out.println("result: " + maxForm + "; predict: " + test.predict);
//        }
//    }
//}
